home *** CD-ROM | disk | FTP | other *** search
/ Mac Easy 2010 May / Mac Life Ubuntu.iso / casper / filesystem.squashfs / usr / share / python-support / python-rdflib / rdflib / sparql / parser.py < prev    next >
Encoding:
Python Source  |  2009-02-22  |  11.4 KB  |  352 lines
  1. """ SPARQL Lexer, Parser and Function-Mapper
  2. By Shawn Brown <http://shawnbrown.com/contact>
  3.  
  4. TO DO:
  5.   swap current parser functions for Michelp's pyparsing setup
  6.   add mapping for FILTER/constraints
  7.   typed literals
  8.   integer, double or boolean abbreviations
  9.   language tags (e.g., @fr)
  10.   nested OPTIONALs ???
  11.   blank node and RDF collection syntax ???
  12.   GRAPH statements ???
  13.  
  14. CURRENTLY SUPPORTED:
  15.   Simple SELECT queries
  16.   Predicate-object and object list shorthand
  17.     (e.g., ?x  foaf:name  ?name ; foaf:mbox  ?mbox ; vcard:TITLE  ?title)
  18.   Multi-line/triple-quoted literals
  19.   BASE, PREFIX, SELECT, WHERE, UNION, OPTIONAL, multiple UNIONs and multiple
  20.     OPTIONALs (but not nested OPTIONALs)
  21.  
  22. USAGE:
  23.     #from sparql_lpm import doSPARQL
  24.     from rdflib.sparql.parser import doSPARQL
  25.     ...load graph...
  26.     ...define SPARQL query as string...
  27.     result = doSPARQL(queryStr, sparqlGr)
  28.  
  29. """
  30.  
  31. import base64
  32. import re
  33. from rdflib.URIRef import URIRef
  34. from rdflib.sparql.graphPattern import GraphPattern
  35.  
  36. def _escape(text): return base64.encodestring(text).replace("\n", "")
  37. def _unescape(text): return base64.decodestring(text)
  38.  
  39. def _escapeLiterals(query):
  40.     """ escape all literals with escape() """
  41.     fn = lambda m: "'" + _escape(m.group(2)) + "'" + m.group(3)
  42.     pat = r"(\"\"\"|'''|[\"'])([^\1]*?[^\\]?)\1" # literal
  43.     return re.sub(pat+"(\s*[.,;\}])", fn, query)
  44.  
  45. def _resolveShorthand(query):
  46.     """ resolve some of the syntactic shorthand (2.8 Other Syntactic Forms) """
  47.     def doList(pat, text):
  48.         pat = re.compile(pat)
  49.         while pat.search(text): text = re.sub(pat, r"\1\2\3 . \2\4", text)
  50.         return text
  51.     # 2.8.1 Predicate-Object Lists
  52.     pat = r"(\{.*?)([^ ]+ )([^ ]+ [^ ]+)\s?; ([^ ]+ [^ ]+\s?[,;\.\}])"
  53.     query = doList(pat, query)
  54.     # 2.8.2 Object Lists
  55.     pat = r"(\{.*?)([^ ]+ [^ ]+ )([^ ]+\s?), ([^ ]+\s?[,\.\}])"
  56.     query = doList(pat, query)
  57.     # TO DO: look at adding all that other crazy stuff!!!
  58.     return query
  59.  
  60. def _resolvePrefixes(query):
  61.     """ resolve prefixed IRIs, remove PREFIX statements """
  62.     # parse PREFIX statements
  63.     prefixes = re.findall("PREFIX ([\w\d]+:) <([^<>]+)>", query) # get list of prefix tuples
  64.     prefixes.extend([
  65.         ("rdf:", "http://www.w3.org/1999/02/22-rdf-syntax-ns#"),
  66.         ("rdfs:", "http://www.w3.org/2000/01/rdf-schema#"),
  67.         ("xsd:", "http://www.w3.org/2001/XMLSchema#"),
  68.         ("fn:", "http://www.w3.org/2004/07/xpath-functions")])
  69.     matches = re.search("PREFIX : <([^<>]+)>", query) # parse colon-only PREFIX
  70.     if matches != None: prefixes.append((":", matches.group(1)))
  71.     query = re.sub("PREFIX [\w\d]*:[ ]?<[^<>]+>[ ]?", "", query) # remove PREFIX statements
  72.     # escape IRIs (unescaped in ??)
  73.     fn = lambda m: "<" + _escape(m.group(1)) + ">"
  74.     query = re.sub("<([^<>]+)>", fn, query)
  75.     # resolve prefixed IRIs
  76.     for pair in prefixes:
  77.         fn = lambda m: "<" + _escape(pair[1]+m.group(1)) + ">" # escaped too
  78.         query = re.sub(pair[0]+"([^ .\}]+)", fn, query)
  79.     return query
  80.  
  81. def _resolveBase(query):
  82.     """ resolve relative IRIs using BASE IRI, remove BASE statement """
  83.     pat = re.compile("BASE <([^<>]+)>\s?")
  84.     base = pat.search(query)
  85.     if base != None:
  86.         fn = lambda m: "<" + base.group(1) + m.group(1) + ">"
  87.         query = re.sub("<([^<>: ]+)>", fn, query) # resolve relative IRIs
  88.         query = re.sub(pat, "", query) # remove BASE statement
  89.     return query
  90.  
  91. def _parseSelect(query):
  92.     """ returns tuple of SELECTed variables or None """
  93.     var = "[?$][\\w\\d]+" # SELECT variable pattern
  94.     select = re.search("SELECT(?: " + var + ")+", query)
  95.     if select != None:
  96.         select = re.findall(var, select.group(0))
  97.         select = tuple(select)
  98.     return select
  99.  
  100. class _StackManager:
  101.     """ manages token stack for _parser() """
  102.     def __tokenGen(self, tokens):
  103.         for token in tokens:
  104.             yield token
  105.     def __init__(self, tokenList):
  106.         self.stack = self.__tokenGen(tokenList)
  107.         self.current = self.stack.next()
  108.     def next(self):
  109.         try:
  110.             self.current = self.stack.next()
  111.             if self.current == "":
  112.                 self.next() # if blank, move to next
  113.         except StopIteration:
  114.             self.current = None
  115.     def token(self):
  116.         return self.current
  117.  
  118. #
  119. # The following classes, _listTypes dictionary and _makeList() function are
  120. # used to test for recognized keywords and to create "typed" lists for nested
  121. # statements when parsing the SPARQL query's WHERE statement
  122. #
  123. class Where(list): pass
  124. class Union(list): pass
  125. class Optional(list): pass
  126. _listTypes = {
  127.     "OPTIONAL": lambda : Optional([]),
  128.     "UNION": lambda : Union([]),
  129.     "WHERE": lambda : Where([])
  130. }
  131. def _makeList(keyword):
  132.     """ return list of given type or None """
  133.     global _listTypes
  134.     if keyword in _listTypes:
  135.         return _listTypes[keyword]()
  136.     return None
  137.  
  138. def _parser(stack, listType="WHERE"):
  139.     """ simple recursive descent SPARQL parser """
  140.     typedList = _makeList(listType)
  141.     nestedType = listType
  142.     while stack.token() != None:
  143.         token = stack.token()
  144.         if _makeList(token) != None:
  145.             nestedType = token
  146.         elif token == "{":
  147.             stack.next() # iterate to next token
  148.             typedList.append(_parser(stack, nestedType))
  149.             nestedType = listType # reset nestedType
  150.         elif token == "}":
  151.             return typedList
  152.         elif token != ".":
  153.             statement = ""
  154.             while token != None and token != "." and token != "{" and token != "}":
  155.                 statement += " " + token
  156.                 stack.next()
  157.                 token = stack.token()
  158.             statement = statement.strip()
  159.             typedList.append(statement)
  160.             continue
  161.         stack.next()
  162.     return typedList
  163.  
  164. def _parseWhere(query):
  165.     """ split query into tokens, return parsed object """
  166.     stackObj = _StackManager(query)
  167.     return _parser(stackObj)
  168.  
  169. def _findStatements(stmntType, stmntList):
  170.     """ recurse over nested list, compile & return flat list of matching
  171.         statement strings used by _getStatements() """
  172.     statements = []
  173.     typedList = _makeList(stmntType)
  174.     for stmnt in stmntList:
  175.         if type(stmnt) is str:
  176.             statements.append(stmnt)
  177.         if type(stmnt) == type(typedList):
  178.             statements.extend(_findStatements(stmntType, stmnt))
  179.     return statements
  180.  
  181. def _getStatements(stmntType, stmntList):
  182.     """ gets statements of given type from given list """
  183.     statements = []
  184.     typedList = _makeList(stmntType)
  185.     for item in stmntList:
  186.         if type(item) == type(typedList):
  187.             statements.append(_findStatements(stmntType, item))
  188.     return statements
  189.  
  190. def _buildGraphPattern(triples):
  191.     # split strings into tuples of strings
  192.     triples = map((lambda x: tuple(re.split(" ", x))), triples)
  193.     # convert tuples of strings into tuples of RDFLib objects
  194.     isIRI = lambda x: x[0]=="<" and x[-1]==">"
  195.     isLit = lambda x: x[0]=="'" and x[-1]=="'" or x[0]=='"' and x[-1]=='"'
  196.     for i in range(len(triples)):
  197.         sub = triples[i][0]
  198.         pred = triples[i][1]
  199.         obj = triples[i][2]
  200.         # unescape and define objects for IRIs and literals
  201.         if isIRI(sub): sub = URIRef(_unescape(sub[1:-1]))
  202.         if isIRI(pred): pred = URIRef(_unescape(pred[1:-1]))
  203.         if isIRI(obj): obj = URIRef(_unescape(obj[1:-1]))
  204.         elif isLit(obj): obj = _unescape(obj[1:-1])
  205.         # build final triple
  206.         triples[i] = (sub, pred, obj)
  207.     return GraphPattern(triples)
  208.  
  209. def _buildQueryArgs(query):
  210.     """ """
  211.     # query lexer
  212.     query = _escapeLiterals(query) # are unescaped in _buildGraphPattern()
  213.     query = re.sub("\s+", " ", query).strip() # normalize whitespace
  214.     query = _resolveShorthand(query) # resolve pred-obj and obj lists
  215.     query = _resolveBase(query) # resolve relative IRIs
  216.     query = _resolvePrefixes(query) # resolve prefixes
  217.     query = re.sub(r"\s*([.;,\{\}])\s*", r" \1 ", query) # normalize punctuation
  218.     whereObj = query[query.find("{")+1:query.rfind("}")].strip() # strip non-WHERE bits
  219.     whereObj = whereObj.split(" ") # split into token stack
  220.     # query parser
  221.     select = _parseSelect(query) # select is tuple of select variables
  222.     whereObj = _parseWhere(whereObj) # stack parsed into nested list of typed lists
  223.     # map parsed object to arrays of RDFLib graphPattern objects
  224.     where = _getStatements("WHERE", [whereObj]) # pass whereObj as nested list
  225.     where.extend(_getStatements("UNION", whereObj))
  226.     where = map(_buildGraphPattern, where)
  227.     optional = _getStatements("OPTIONAL", whereObj)
  228.     optional = map(_buildGraphPattern, optional)
  229.     # run query
  230.     #return sparqlGr.query(select, where, optional)
  231.     return { "select":select, "where":where, "optional":optional }
  232.  
  233. def doSPARQL(query, sparqlGr):
  234.     """ Takes SPARQL query & SPARQL graph, returns SPARQL query result object. """
  235.     x = _buildQueryArgs(query)
  236.     return sparqlGr.query(x["select"], x["where"], x["optional"])
  237.  
  238.  
  239. if __name__ == "__main__":
  240.     testCases = [
  241. # basic
  242. """
  243. SELECT ?name
  244. WHERE { ?a <http://xmlns.com/foaf/0.1/name> ?name }
  245. """,
  246. # simple prefix
  247. """
  248. PREFIX foaf: <http://xmlns.com/foaf/0.1/>
  249. SELECT ?name
  250. WHERE { ?a foaf:name ?name }
  251. """,
  252. # base statement
  253. """
  254. BASE <http://xmlns.com/foaf/0.1/>
  255. SELECT ?name
  256. WHERE { ?a <name> ?name }
  257. """,
  258. # prefix and colon-only prefix
  259. """
  260. PREFIX : <http://xmlns.com/foaf/0.1/>
  261. PREFIX vcard: <http://www.w3.org/2001/vcard-rdf/3.0#>
  262. SELECT ?name ?title
  263. WHERE {
  264.     ?a :name ?name .
  265.     ?a vcard:TITLE ?title
  266. }
  267. """,
  268. # predicate-object list notation
  269. """
  270. PREFIX foaf: <http://xmlns.com/foaf/0.1/>
  271. SELECT ?name ?mbox
  272. WHERE {
  273.     ?x  foaf:name  ?name ;
  274.         foaf:mbox  ?mbox .
  275. }
  276. """,
  277. # object list notation
  278. """
  279. PREFIX foaf: <http://xmlns.com/foaf/0.1/>
  280. SELECT ?x
  281. WHERE {
  282.     ?x foaf:nick  "Alice" ,
  283.                   "Alice_" .
  284. }
  285. """,
  286. # escaped literals
  287. """
  288. PREFIX tag: <http://xmlns.com/foaf/0.1/>
  289. PREFIX vcard: <http://www.w3.org/2001/vcard-rdf/3.0#>
  290. SELECT ?name
  291. WHERE {
  292.     ?a tag:name ?name ;
  293.        vcard:TITLE "escape test vcard:TITLE " ;
  294.        <tag://test/escaping> "This is a ''' Test \"\"\"" ;
  295.        <tag://test/escaping> ?d
  296. }
  297. """,
  298. # key word as variable
  299. """
  300. PREFIX foaf: <http://xmlns.com/foaf/0.1/>
  301. SELECT ?PREFIX ?WHERE
  302. WHERE {
  303.     ?x  foaf:name  ?PREFIX ;
  304.         foaf:mbox  ?WHERE .
  305. }
  306. """,
  307. # key word as prefix
  308. """
  309. PREFIX WHERE: <http://xmlns.com/foaf/0.1/>
  310. SELECT ?name ?mbox
  311. WHERE {
  312.     ?x  WHERE:name  ?name ;
  313.         WHERE:mbox  ?mbox .
  314. }
  315. """,
  316. # some test cases from grammar.py
  317. "SELECT ?title WHERE { <http://example.org/book/book1> <http://purl.org/dc/elements/1.1/title> ?title . }",
  318.  
  319. """PREFIX foaf: <http://xmlns.com/foaf/0.1/>
  320. SELECT ?name ?mbox
  321. WHERE { ?person foaf:name ?name .
  322. OPTIONAL { ?person foaf:mbox ?mbox}
  323. }""",
  324.  
  325. """PREFIX foaf: <http://xmlns.com/foaf/0.1/>
  326. SELECT ?name ?name2
  327. WHERE { ?person foaf:name ?name .
  328. OPTIONAL { ?person foaf:knows ?p2 . ?p2 foaf:name   ?name2 . }
  329. }""",
  330.  
  331. """PREFIX foaf: <http://xmlns.com/foaf/0.1/>
  332. #PREFIX rdf: <http://www.w3.org/1999/02/22-rdf-syntax-ns#>
  333. SELECT ?name ?mbox
  334. WHERE
  335. {
  336. { ?person rdf:type foaf:Person } .
  337. OPTIONAL { ?person foaf:name  ?name } .
  338. OPTIONAL {?person foaf:mbox  ?mbox} .
  339. }"""
  340.     ]
  341.  
  342.     print "Content-type: text/plain\n\n"
  343.     for query in testCases:
  344.         print "\n-----\n"
  345.         print '>>> query = """' + query.replace("\n", "\n... ") + '"""'
  346.         print ">>> result = doSPARQL(query, sparqlGr)\n"
  347.         result = _buildQueryArgs(query);
  348.         print "select = ", result["select"], "\n"
  349.         print "where = ", result["where"], "\n"
  350.         print "optional = ", result["optional"], "\n"
  351.         print "result = sparqlGr.query(select, where, optional)"
  352.